The present invention relates to an arithmetic apparatus which is incorporated in a mobile communication apparatus, and a digital signal processor and a radio station apparatus such as a mobile radio station and a base radio station in that the arithmetic apparatus is incorporated. More particularly, the invention relates to a structure which is capable of efficiently performing a Viterbi decoding process.
In recent years, digital signal processors (hereinafter called "DSP") have been widely used as processors of a type arranged to be built in a device, such as a portable telephone, in the movement of digitization in the mobile communication field. Since bit errors are frequently generated in data communication through a mobile radio communication line, an error correction process must be performed. As a method of correcting an error, a method may be employed in which a convolutional code generated from an input bit is decoded by the receiver side by Viterbi decoding. The error correction process is performed by using the DSP.
Viterbi decoding is performed by repeating simple processes, such as addition, comparison and selection and by performing a trace back operation for finally decoding data so that maximum likelihood decoding of a convolutional code is realized. The Viterbi decoding process will briefly be described.
The convolutional code is generated by mod2 addition of an input bit and a predetermined number of bits previous to the input bit to each other so that a plurality of coded data items are generated to correspond to one input bit. The number of input information bits affecting the coded data is called a "constraint length K", the number of which is the same as the shift registers for use to perform the mod2 addition.
Coded data is determined by the states of the input bit and the preceding (K-1) input bits. The foregoing state is shifted (transition is made) to a new state when a new information bit is supplied. The state, in which the transition is permitted, is determined whether the new input bit is 0 or 1. The number of the states is 2.sup.K-1 because each of (K-1) bits can be made to be 1 or 0.
Viterbi decoding is arranged such that a received coded data series is observed and the most probable state is estimated from all of the state transitions which are able to take place. Whenever coded data (a received data series) corresponding to one information bit is obtained, the signal distance (metric) from the path to each state at this time is therefore calculated. Operations are sequentially repeated in each of which a path having smaller metric of the paths is left as a survival path.
FIG. 17 shows a state in a convolution coder having constraint length K in which two paths each indicating a state transition extends, to a certain state S[2n] (n is a positive integer) at a certain moment, from states S[n] previous to the state S[2n] by one state and S[n+2.sup.K-2 ]. An example case where K=3 will now be described. When n=1, transitions from S[1], that is, state S01, and S[3], that is, state S11, can be performed to S[2], that is, state S10 (a state where two preceding bits have been sequentially been input in the order as "1" and "0") are permitted. In a case where n=2, transitions from S[2], that is, state S10, and S[4], that is, state S00, to S[4], that is, state S00 (a state expressed by two lower bits) are permitted.
Path metric a is the sum of inter-signal distance (branch metric x) from an output symbol of a path input to state S[2n] and a received data series and path metric A which is the total sum of the branch metrics of survival paths to state S[n] previous to state S[2n].
Similarly, path metric b is the sum of inter-signal distance (branch metric y) from an output symbol of a path input to state S[2n] and a received data series and path metric B which is the total sum of the branch metrics of survival paths to state S[n+2.sup.K-2 ] previous to state S[2n].
The thus-obtained path metrics a and b which are input to state S[2n] are subjected to a comparison to select smaller path metric as a survival path.
Viterbi decoding is structured such that each of the additions for obtaining the path metric, comparisons of the path metrics and selections of the path metric is performer for 2.sup.K-1 states at each time.
Moreover, a history of results of selections of the paths must be stored as path select signal PS[i], [i=0 to 2.sub.K-1 ]. If the suffix (for example, n) of the state previous to the selected path is smaller than suffixes (n+2.sup.K-2) of the state previous to the non-selected path, PS[i]=0. If the foregoing suffix is larger, PS[i]=1. Since n&lt;(n+2.sup.K-2) in the case shown in FIG. 17, state S[n+2.sup.K-2 ] is selected if a.gtoreq.b so that PS[S2n]=1. If a&lt;b, then state S[n] is selected so that PS[S2n]=0.
When decoding is finally performed by tracing back, data is decoded while tracing back the survival paths on the basis of the path select signals.
Referring to FIG. 18, the tracing back process will briefly be described. FIG. 18 shows a state of tracing back the path from state S[2n] (n is a positive integer) to state S[n] at a previous time or state S[n+2.sup.K-2 ] in accordance with path select signal PS[2n].
In general, in use of state S[i] and path select signal PS[i], a previous state is expressed as S[i/2+PS[i].times.2.sup.K-2 ]. If convolutional code terminated at a tail bit thereof is used, the path select signal is made to be 0 when coded data at the previous time is 0. The path select signal is made to be 1 when coded data at the previous time is 1. Therefore the foregoing path select signal can be used as coded data.
The conventional arithmetic unit in the DSP for performing Viterbi decoding, as shown in FIG. 15, comprise a data memory 1 for storing path metrics, path select signal and coded data; a barrel shifter 3 for shifting data read from the data memory 1; a first bus 2 connected to the data memory 1 to supply data and transfer a result of a calculation; a first register 23 for storing the number of bits which are shifted by the barrel shifter 3; an arithmetic logical circuit (hereinafter called as an "ALU") 26 for executing a arithmetic logic operations; a first latch 24 for temporarily storing the value of the left-hand input of the ALU 26; a second latch 25 for temporarily storing the value of the right-hand input of the ALU 26; second registers 27 and 28 for temporarily storing a result of the calculation; and a second bus 12 for supplying data from the register 27 or the register 28.
The number of bits which are shifted by the barrel shifter 3 is expressed by two's complementary system. When the value is a positive number, right shift is performed. When the value is a negative number, left shift is performed.
A tracing back operation, which is performed when Viterbi decoding of coded data obtained by convolutional coding, which is terminated at a tail bit, is performed by the above-mentioned arithmetic unit, will now be described.
The conditions at this time are assumed such that the constraint length of the convolutional code is K, the number of coded information bit is n and the bit width in each of the data memory 1, the first bus 2, the second bus 12, the first latch 24, the second latch 25, the ALU 26 and the second registers 27 and 28 is 2.sup.K-1 bits.
Path select signal PSt[i] (t=0 to {(n-1)+(K-1)}, i=0 to {2.sup.K-1 }) at time t is stuffed into one word as pass memory PM[t]={PSt[2.sup.K-1 -1], PSt[2.sup.K-1 -2], . . . , PSt[1], PSt[0]} so as to be formed into PM[t], (t=0 to {(n-1)+(K-1)}) and stored in the data memory 1.
Decoded data Y[i] (i=0 to {n-1}) is stored in the date memory 1 in such a way that one bit is made to be one word.
The tracing back operation is performed in such a way that PM[t] is read from the data memory 1; a selected path select signal is shifted to the least significant bit (LSB) by the barrel shifter 3; and then the LSB is extracted and made to be decoded data. The number of shifts is obtained with the complement of 2 of the selected state. Since the foregoing convolutional code is structured to be terminated at the tail bit, the operation starts at state 0. The previous state is obtained by calculating [i/2+PS[i].times.2.sup.K-2 ]. In accordance with the obtained state, the number of shifts required when a next path select signal is shifted to the LSB is obtained. The foregoing procedure is repeated so that a decoded code series is obtained.
The steps of the tracing back operation will now be described.
Step 1: To start the operation at state 0, fixed value "0" is stored in the second latch 25. The ALU 26, as it is, stores the value in the second latch 25 into the second register 27.
From next step 2 to step 10, the operations are repeated n times while decreasing the value of i from {(n-1)+(K-1)} to (K-1).
Step 2: The value in the second register 27 is, through the second bus 12, stored in the first latch 24. The ALU 26 obtains the two's complement of the value in the first latch 24 to store the obtained value in the second register 28.
Step 3: The value in the second register 28 is, through the first bus 2, stored in the first register 23. Thus, the value is the number of shift bits for selecting a next path select signal.
Step 4: The path memory PM[i] is read from the data memory 1, and then shifted by the barrel shifter 3 by the number of shift bits instructed by the first register 23. Then, the value is stored in the second latch 25. The ALU 26, as it is, stores the value in the second latch 25 in the second register 28. Thus, the selected path select signal is approached to the least significant bit [LSB].
Step 5: The value in the second register 28 is, through the second bus 12, stored in the first latch 24, and then fixed value "1" is stored in the second latch 25. The ALU 26 obtains the logical product of the first latch 24 and the second latch 25 to store a result in the second register 28 (only the LSB is extracted).
Step 6: The value in the second register 28 is, as decoded data Y[i-(k-1)], stored in the data memory 1 (the LSB is made to be decoded data).
Step 7: Fixed value "K" is stored in the first register 23.
Step 8: The value in the second register 27 is, through the second bus 12, stored in the first latch 24. Then, the value in the second register 28, is through the first bus 2 output to the barrel shifter 3. The barrel shifter 3 shifts the supplied value by the number of shift bits instructed by the first register 23 to store the output therefrom in the second latch 25. The ALU 26 obtains the logical sum of the first latch 24 and the second latch 25 to store a result in the second register 28.
Step 9: Fixed value "-1" is stored in the first register 23.
Step 10: The barrel shifter 3 shifts the value in the second register 28 by the number of shift bits instructed by the first register 23 so that an output is obtained which is stored in the second latch 25. The ALU 26, as it is, stores the value in the second latch 25 in the second register 27 (steps 7 to 10 enable a previous state to be calculated).
As described above, the conventional arithmetic unit is structured to perform the calculation by combining the barrel shifter 3 and the ALU 26 so that the tracing back operation for Viterbi decoding n-bit information bits is completed in (9n+1) steps.
However, the above-mentioned conventional arithmetic unit suffers from a problem in that a great number of execution steps must be performed to complete the tracing back operation. A arithmetic unit, which is capable of overcoming the foregoing problem, has been disclosed in, for example Unexamined Japanese Patent Publication 6-112848.
The foregoing arithmetic unit, as shown in FIG. 16, comprises: a data memory 1 for storing path metrics, path select signals and the like; a bus 2 connected to the data memory 1 and arranged to supply data and to transfer a result of the calculation; a barrel shifter 3 for shifting a selected path select signal of path memory data read from the data memory 1 to the most significant bit (MSB); a shift register 4 for shift-receiving the MSB of the output from the barrel shifter 3 and load data from the data memory 1 through the bus 2 or storing data into the data memory 1; and an invertor 29 for inverting the values of a predetermined plural bit positions in the shift register 4 to supply the same as the number of shift bits to the barrel shifter 3.
The number of bits which are shifted by the barrel shifter 3 is expressed by a two's complementary system. When the value is a positive number, the right shift is performed. When the value is a negative number, left shift is performed. The shift register 4 is structured such that its shift input side is the MSB.
A tracing back operation, which is performed when Viterbi decoding of coded data obtained by convolutional coding, which is terminated at a tail bit, is performed by the above-mentioned arithmetic unit, will now be described.
The conditions at this time are assumed such that the constraint length of the convolutional code is K, the number of coded information bit is n and the bit width in each of the data memory 1, the bus 2 and shift register 4 is 2.sup.K-1 bits. The MSB, which is the output from the barrel shifter 3 is supplied to the shift input of the shift register 4. The second register 28 inverts (K-1) upper bits in the shift register 4, and then outputs K bits, which is the sum obtained by adding "0" to the MSB of (K-1) bits output from the shift register 4, as the number of shift bits.
Similarly to the above-mentioned unit, path select signal PSt[i] (t=0 to {(n-1)+(K-1)}, i=0 to {2.sup.K-1 -1}) is stuffed into one word as pass memory PM[t]={PSt[2.sup.K-1 -1], PSt[2.sup.K-1 -2], . . . , PSt[1], PSt[0]} so as to be formed into PM[t], (t=0 to {(n-1)+(K-1)}) and stored in the data memory 1. Decoded data Y[i] (i=0 to {n-1}) is stored in the data memory 1 in such a way that one bit is made to be one word.
The tracing back operation is performed in such a way that the path memory read from the data memory 1 is shifted by the barrel shifter 3 so that the path select signal, which must be selected, is shifted to the MSB. Then, the shifted path select signal is supplied to the shift register 4. At this time, (K-1) upper bits in the shift register 4 indicate a previous state. Therefore, a next number of shifts can be obtained by inverting the (K-1) upper bits. The foregoing number of shifts is generated by the invertor 29. Then, a path select signal, which must be selected in a next path memory, is shifted to the MSB of the output from the barrel shifter 3 to supply the shifted path select signal to the shift register 4.
The foregoing operation is repeated so that the selected path select signals, which serve as decoded data, are sequentially stored in the shift register 4. Whenever a predetermined number of bits has been stored, they are stored in the data memory 1.
The steps of the tracing back operation will now be described.
Step 1: To start the operation at state 0, data of fixed value "0" is loaded to be stored in the shift register 4.
From next steps 2 and 3, the operations are repeated n times while decreasing the value of i from {(n-1)+(K-1)} to (K-1).
Step 2: The path memory PM[i] is read from the data memory 1, and then shifted by the barrel shifter 3 by the number of shift bits instructed with K bits, which are output from the invertor 29. Then, the MSB of the output fromn the barrel shifter 3 is shift-input to the shift register 4. Thus, the foregoing operation causes the path select signal, which must be selected, is approached to the most significant bit [MSB]. In this case, [K-1] upper bits of the shift register 4, to which the shift-input has been made, indicates the previous state. Inversion of [K-1] upper bits is the basis of the number of shift bits for selecting a next pat select signal.
Step 3: Whenever 2.sup.K-1 bits are decoded, the contents of the shift register 4 are, one time, stored in the data memory 1, Thus, the path select signal selected and stored in the shift register 4 is made to be decoded data.
As described above, the above-mentioned unit is arranged such that the selection of the path select signal and calculation of the previous state are performed in step 2. Therefore, the tracing back process in the Viterbi decoding of n-bit information bits can be completed in {n+(n/2.sup.K-1)+1} steps.
However, the above-mentioned conventional arithmetic units are structured on a condition that the bit width of the data memory and the bus must be 2.sup.K-1 (K is a constraint length of the convolutional code required to be decoded) or greater. Thus, there arises a problem in that enlargement of the value of K arises a necessity of enlarging the width of the bit in the data path.